package dynamicprogramming;


import com.sun.rowset.internal.Row;

import java.awt.color.ColorSpace;

/**
 * @Author: LDeng
 * @Date: 2021-04-25 14:18
 */

//求最长公共子序列
public class LCS {
    public static void main(String[] args) {

        String s1="oxcpqrsvwf";
        String s2="shmtulqrypy";
        int lcs = lcs(new int[]{111, 120, 99, 112 ,113 ,114, 115 ,118, 119, 102},
                      new int[]{115 ,104 ,109, 116, 117 ,108, 113, 114, 121 ,112 ,121});
        int lcs1 = lcs1(new int[]{111, 120, 99, 112 ,113 ,114, 115 ,118, 119, 102},
                        new int[]{115 ,104 ,109, 116, 117 ,108, 113, 114, 121 ,112 ,121});
        int lcs2 = lcs2(new int[]{111, 120, 99, 112 ,113 ,114, 115 ,118, 119, 102},
                        new int[]{115 ,104 ,109, 116, 117 ,108, 113, 114, 121 ,112 ,121});
        int lcs3 = lcs3(new int[]{111, 120, 99, 112 ,113 ,114, 115 ,118, 119, 102},
                        new int[]{115 ,104 ,109, 116, 117 ,108, 113, 114, 121 ,112 ,121});
        int lcs4 = lcs4(s1,s2);
        int lcs5 = lcs5(new int[]{111, 120, 99, 112 ,113 ,114, 115 ,118, 119, 102},
                new int[]{115 ,104 ,109, 116, 117 ,108, 113, 114, 121 ,112 ,121});
        System.out.println("递归实现=> lcs:" + lcs);
        System.out.println("动态规划实现=> lcs1:" + lcs1);
        System.out.println("滚动数组实现=> lcs2:" + lcs2);
        System.out.println("一维数组实现=> lcs3:" + lcs3);
        System.out.println("一维数组实现 字符串参数=> lcs4:"+lcs4);
        System.out.println("一维数组实现 行列转换=> lcs5:"+lcs5);

    }

    //一维数组+三个变量 优化空间 ， 行列转换，用短边做行
    static int lcs5(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) return 0;
        if (num2 == null || num2.length == 0) return 0;
        int rows=0;
        int cols=0;
        int[] rowsNums=num1;
        int[] colsNums=num2;
        if(num1.length>num2.length){
            colsNums=num2;  rowsNums=num1;
        }else{
            colsNums=num1;  rowsNums=num2;
        }
        int[] dp = new int[colsNums.length + 1];
        for (int i = 1; i <= rowsNums.length; i++) {
            int current=0;
            for (int j = 1; j <= colsNums.length; j++) {
                int leftTop=current;
                current=dp[j];
                if (rowsNums[i - 1] == colsNums[j - 1]) {//相等，取左上+1
                    dp[j] = leftTop + 1;
                } else {//不等，选左边或者上面的大的数值覆盖
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[colsNums.length];
    }


    //一维数组+current/leftTop变量 优化空间
    static int lcs4(String text1, String text2) {
        char[] num1=text1.toCharArray();
        char[] num2=text2.toCharArray();
        if (num1 == null || num1.length == 0) return 0;
        if (num2 == null || num2.length == 0) return 0;
        int[] dp = new int[num2.length + 1];
        for (int i = 1; i <= num1.length; i++) {
            int current=0;
            for (int j = 1; j <= num2.length; j++) {
                int leftTop=current; //current 指向的值拿出来赋值给leftTop,
                current=dp[j]; //current 指向dp[j]
                if (num1[i - 1] == num2[j - 1]) {//相等，取左上+1
                    dp[j] = leftTop + 1;
                } else {//不等，选左边或者上面的大的数值覆盖
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[num2.length];
    }

    //一维数组+三个变量 优化空间
    static int lcs3(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) return 0;
        if (num2 == null || num2.length == 0) return 0;
        int[] dp = new int[num2.length + 1];
        for (int i = 1; i <= num1.length; i++) {
            int current=0;
            for (int j = 1; j <= num2.length; j++) {
                int leftTop=current;
                current=dp[j];
                if (num1[i - 1] == num2[j - 1]) {//相等，取左上+1
                    dp[j] = leftTop + 1;
                } else {//不等，选左边或者上面的大的数值覆盖
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[num2.length];
    }


    //滚动数组, 优化空间
    static int lcs2(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) return 0;
        if (num2 == null || num2.length == 0) return 0;
        int[][] dp = new int[2][num2.length + 1];
        for (int i = 1; i <= num1.length; i++) {
            int row = i % 2;
            int prevRow = (i - 1) % 2;
            for (int j = 1; j <= num2.length; j++) {
                if (num1[i - 1] == num2[j - 1]) {
                    dp[row][j] = dp[prevRow][j - 1] + 1;
                } else {
                    dp[row][j] = Math.max(dp[prevRow][j], dp[row][j - 1]);
                }
            }
        }
        return dp[num1.length % 2][num2.length];
    }


    //动态规划实现
    static int lcs1(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) return 0;
        if (num2 == null || num2.length == 0) return 0;
        int[][] dp = new int[num1.length + 1][num2.length + 1];
        for (int i = 1; i <= num1.length; i++) {
            for (int j = 1; j <= num2.length; j++) {
                if (num1[i - 1] == num2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[num1.length][num2.length];
    }

    //递归实现
    static int lcs(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) return 0;
        if (num2 == null || num2.length == 0) return 0;
        return lcs(num1, num1.length, num2, num2.length);//递归
    }

    /**
     * 求nums1 前i个元素和 nums2前j个元素的最长公共子序列长度
     *
     * @param nums1
     * @param i
     * @param nums2
     * @param j
     */
    static int lcs(int[] nums1, int i, int[] nums2, int j) {
        //递归基
        if (i == 0 || j == 0) return 0;
        if (nums1[i - 1] == nums2[j - 1]) {//如果这两个元素相等， 就拿出顶到前面一个元素的最长公共子序列的长度+1
            return lcs(nums1, i - 1, nums2, j - 1) + 1;
        }
        return Math.max(lcs(nums1, i - 1, nums2, j),
                lcs(nums1, i, nums2, j - 1));
    }


}
